package com.berchen.test;

/**
 * 合并两个有序链表
 */
public class MergeLinkedList {

    public static void main(String[] args) {

        ListNode1 list1=new ListNode1(1);
        ListNode1 list2=new ListNode1(3);
        ListNode1 list3=new ListNode1(7);
        list1.next=list2;
        list2.next=list3;

        ListNode1 list=new ListNode1(2);
        MergeLinkedList mergeLinkedList = new MergeLinkedList();
        ListNode1 merge = mergeLinkedList.Merge(list1, list);
        while (merge!=null){
            System.out.println(merge.val);
            merge=merge.next;
        }
    }
    public ListNode1 Merge(ListNode1 list1,ListNode1 list2) {
        ListNode1 head=new ListNode1(0);
        ListNode1 temp1=list1;
        ListNode1 temp2=list2;
        while(temp1!=null&&temp2!=null){
            if(temp1.val<temp2.val){
                merge(head,new ListNode1(temp1.val));
                temp1=temp1.next;
            }else {
                merge(head,new ListNode1(temp2.val));
                temp2=temp2.next;
            }
        }
        while(temp1!=null){
            merge(head,new ListNode1(temp1.val));
            temp1=temp1.next;
        }
        while(temp2!=null){
            merge(head,new ListNode1(temp2.val));
            temp2=temp2.next;
        }
        return head.next;
    }
    public void merge(ListNode1 head,ListNode1 node){

        ListNode1 temp=head;
        while(temp.next!=null){
            temp=temp.next;
        }
        temp.next=node;
    }
}
class ListNode1 {
    int val;
    ListNode1 next = null;

    ListNode1(int val) {
        this.val = val;
    }
}
